package dynamicProgramming.DoubleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/22 10:04
 **/

import javax.swing.text.TabExpander;

/**
 * 题目 ：字符串交织
 * 题目详述 ：
 * 给定三个字符串s1、s2、s3，请判断s3能不能由s1和s2交织（交错）组成。
 * 两个字符串 s 和 t 交织的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 提示：a + b 意味着字符串 a 和 b 连接。
 *
 * 提示：
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 */
public class IsInterleave {
    /**
     * 思路 ：
     * 使用迭代来判断是否能够字符串s1和字符串s2能否交织成为字符串s3;
     * 需要注意的是，若是要去求解f(i + 1,j + 1)的值，则只需要知道f(i , j + 1) && f(i + 1,j);
     *
     * 状态转移方程 ：
     * 注意 ：假设f(i + 1,j + 1)为长度为i + 1的字符串s1和长度为j + 1的字符串s2能否能够编织成字符串s3（长度为i + j + 2）;
     * （2）若是字符串s3中正在遍历的字符与字符串s1中正在遍历的字符相同的话，即
     * ===》 f(i + 1,j + 1) = f(i,j + 1);
     * f(i + 1,j + 1)是取决于f(i,j + 1),即长度为i的字符串s1和长度为j + 1的字符串s2是否能够编织成字符串s3;
     * （3）若是字符串s3中正在遍历的字符与字符串s2中正在遍历的字符相同的话，即
     * ===》f(i + 1,j + 1) = f(i + 1,j);
     * f(i + 1,j + 1)是取决于f(i + 1,j)，即长度为i + 1的字符串s1和长度为j的字符串s2是否能够编织成字符串s3：
     * （4）若是字符串s3中正在遍历的字符与字符串s1/s2中正在遍历的字符都不相同的话，
     * ===》即，f(i + 1,j + 1) == false;
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        // 假设f(i + 1，j + 1)为字符串s1[0...i]和字符串s2[0...j]是否能够交织成字符串s3[0...(i+j+1)];
        // 若是字符串s1长度 + 字符串s2的长度 != 字符串s3的长度的话，那么字符串s1和字符串s2必然不可能编织成字符串s3;
        if(len1 + len2 != len3){
            return false;
        }
        // 即，使用temp[2][len2 + 1]的二维数组来存储;
        // 即，若是要求解f(i + 1,j + 1)的话，则需要知道f(i + 1,j) && f(i , j + 1);
        boolean[][] temp = new boolean[2][len2 + 1];
        // （1）对于f(i , j)进行初始化赋值;（即，当前字符串s1和字符串s2都是空字符串的话，那么其必然能够编织成空字符串）
        temp[0][0] = true;
        // （2）对于f（-1 ， j）进行初始化;
        // （即，当s1字符串为空字符串情况下，s2的子字符串t2[0...(j-1)]是否与s3的子字符串t3[0...(j-1)相等]）
        for(int j = 0 ; j < len2 ; j++){
                temp[0][j + 1] = s2.substring(0 , j + 1).equals(s3.substring(0 , j + 1)) ? true : false;
        }
        // 迭代 ：实现遍历字符串s1和字符串s2中的所有字符;同时将f(i , j)的结果存储到对应的temp[i + 1][j + 1]中;
        for(int i = 0 ; i < len1 ; i++){
            // （3）对于f(i , -1) && f(i + 1 , -1)进行初始化;
            // （即，当s2字符串为空字符串的情况下，s1的子字符串t1[0...(i-1)]是否与s3的子字符串t3[0...(i-1)相等]）
            temp[i % 2][0] = (i == 0) || s1.substring(0 , i + 1).equals(s3.substring(0 , i + 1)) ? true : false;
            temp[(i + 1) % 2][0] = s1.substring(0 , i + 1).equals(s3.substring(0 , i + 1)) ? true : false;
            for(int j = 0 ; j < len2 ; j++){
                // 需要去判断是否字符串s3中正在遍历的字符是否可以在字符串s1和s2中被遍历到;
                temp[(i + 1) % 2][j + 1] = (s1.charAt(i) == s3.charAt(i + j + 1) && temp[i % 2][j + 1])
                        || (s2.charAt(j) == s3.charAt(i + j + 1) && temp[(i + 1) % 2][j]);
            }
        }
        // 返回值为temp[len1 % 2][len2],其所存储的是 长度为len1的字符串s1 和 长度为len2的字符串s2是否能够编织成字符串s3;
        return temp[len1 % 2][len2];
    }
}
